#include <iostream>
#include <vector>

using std::cout;
using std::endl;
using std::vector;

//选择排序
void selectSort(vector<int> array)
{
	int i, j, min;
	int size = array.size();

	for(i = 0; LT(i, size); i++)
	{
		min = i;
		for(j = i; LT(j, size); j++)
			if(LT(array[j], array[min]))
				min = j;
		if(!EQ(i, min))
			SWAP(array[i], array[min]);
	}	
}

//插入排序
void insertSort(vector<int> array)
{
	int i, j;
	int size = array.size(), min;

	for(i = 1; LT(i, size); i++)
	{
		min = array[i];
		for(j = i-1; GTE(j, 0)&&GT(array[j], min); j--)
			array[j+1] = array[j];
		array[j+1] = min;
	}
}

//折半插入排序
void binsertSort(vector<int> array)
{
	int i, j;
	int left, right, mid, cur, size = array.size();
	
	for(i = 1; LT(i, size); i++)
	{
		left = 0;
		right = i-1;
		cur = array[i];
		while(LTE(left, right))
		{
			mid = (left+right)/2;
			if(LT(cur, array[mid]))
				right = mid-1;
			else
				left = mid+1;
		}
		for(j = i; GT(j, left); j--)
			array[j] = array[j-1];
		array[j] = cur;
	}
}

//起泡排序
void bubbleSort(vector<int> array)
{
	int i, j;
	int size = array.size();
	for(i = 0; LT(i, size); i++)
		for(j = size-1; GT(j, i); j--)
			if(LT(array[j], array[j-1]))
				SWAP(array[j], array[j-1]);
}

//快速排序
void qsort(vector<int> &, int, int);

void quickSort(vector<int> array)
{
	int size = array.size();
	qsort(array, 0, size-1);
	// vector<int>::iterator p;
	// for(p = array.begin(); p != array.end(); p++)
	// 	cout << *p << " ";
}

void qsort(vector<int> &array, int beg, int end)
{
	int i, j, x;
	i = beg;
	j = end;
	x = array[(beg+end)/2];
	while(LTE(i, j))
	{
		while(LT(array[i], x))
			i++;
		while(GT(array[j], x))
			j--;
		if(LTE(i, j))
		{
			SWAP(array[i], array[j]);
			i++;
			j--;
		}
	}
	if(GT(j, beg))
		qsort(array, beg, j);
	if(LT(i, end))
		qsort(array, i, end);
}

//堆排序
void maxHeapify(vector<int> &, int, int);

void heapSort(vector<int> array)
{
	int size = array.size()-1;
	for(int i = size/2; GTE(i, 0); i--)
		maxHeapify(array, i, size);
	for(int i = size; GTE(i, 0); i--)
	{
		SWAP(array[0], array[i]);
		maxHeapify(array, 0, i);
	}
	// vector<int>::iterator p;
	// for(p = array.begin(); p != array.end(); p++)
	// 	cout << *p << " ";
}

void maxHeapify(vector<int> &array, int i, int size)
{
	int left = 2*i+1, right = 2*i+2, max;
	max = i;
	if(LT(left, size) && GT(array[left], array[max]))
		max = left;
	if(LT(right, size) && GT(array[right], array[max]))
		max = right;
	if(!EQ(max, i))
	{
		SWAP(array[i], array[max]);
		maxHeapify(array, max, size);
	}
}

//归并排序
void msort(vector<int> &, int, int);
void merge(vector<int> &, int, int, int, int);

void mergeSort(vector<int> array)
{
	msort(array, 0, array.size()-1);
}

void msort(vector<int> &array, int start,int end)
{
	if(EQ(start, end))
	 	return;
	int t;
	t = (start+end)/2;
	msort(array, start, t);
	msort(array, t+1, end);
	merge(array, start, t, t+1, end);	
}

void merge(vector<int> &array, int as, int ae, int bs, int be) 
{
	int i, ap, bp, size;
	vector<int> temp;
	ap = as;
	bp = bs;
	while(LTE(ap, ae) && LTE(bp, be))
	{
		if(array[ap] < array[bp])
		{
			temp.push_back(array[ap]);
			ap++;
		}
		else
		{
			temp.push_back(array[bp]);
			bp++;
		}
	}
	if(!LTE(ap, ae))
		while(LTE(bp, be))
		{
			temp.push_back(array[bp]);
			bp++;
		}
	if(!LTE(bp, be))
		while(LTE(ap, ae))
		{
			temp.push_back(array[ap]);
			ap++;
		}
	size = temp.size();
	for(i = 0; LT(i, size); i++)
		array[as+i] = temp[i];
}